package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/2/8 11:56
 */
public class No441_排列硬币 {
    public static void main(String[] args) {
        Solution441 solution441 = new Solution441();
        //返回满足行数
        int i = solution441.arrangeCoins(9);
        System.out.println(i);
    }
}


class Solution441 {
    public int arrangeCoins(int n) {
        //二分查找:区间查找
        //模板
        long left = 0;
        long right = n;

        //如何左开右闭??

        //左闭右闭
        while (left <= right) {
            //解决溢出问题
            long mid = left + (right - left) / 2;
            //等差数列求和
            long check = (1 + mid) * mid / 2;

            //切分
            //[left,right]->[left,mid],[mid,right]
            if (check > n) {
                //对right进行处理
                right = mid - 1;
            } else if (check < n) {
                //对left进行处理
                left = mid + 1;
            } else {
                return (int) mid;
            }
        }
        //left > right
        //最后返回的结果必须在区间内
        //[left,right]
        return (int) right;
    }
}



    //public int arrangeCoins(int n) {
    //
    //    //由于左闭右开,特殊处理
    //    if (n == 0 || n == 1) {
    //        return n;
    //    }
    //
    //    //二分查找:本质型二分查找
    //    //本质:区间查找
    //    //模板
    //    long left = 0;
    //    long right = n;
    //
    //    //left,right = [0,1)
    //
    //    //左闭右开
    //    //[left,right)
    //    while (left < right) {
    //        //解决溢出问题
    //        long mid = left + (right - left) / 2;
    //        //等差数列求和
    //        long check = (1 + mid) * mid / 2;
    //
    //        //[left,right)->[left,mid),[mid,right)
    //        if (check > n) {
    //            //对right进行处理
    //            right = mid;
    //        } else if (check < n) {
    //            //对left进行处理
    //            left = mid + 1;
    //        } else {
    //            return (int) mid;
    //        }
    //    }
    //    //当区间没有的时候出来
    //    //[left,right) -> left==right的时候,区间没有了
    //    return (int) (right - 1);
    //}



    //public int arrangeCoins(int n) {
    //    //18->5
    //    //1+2+3+4+5+6 = 21 > 18? -> 5
    //
    //    //结果行
    //    int res = 0;
    //    //n>0,没减完,说明还能排
    //    while (n > 0) {
    //        res++;
    //        n -= res;
    //    }
    //    //减完刚好是0
    //    //6-1-2-3 = 0 -> 3
    //    //减完小于0
    //    //5-1-2-3 <0 -> 2
    //
    //    if (n == 0) {
    //        return res;
    //    } else {
    //        return res - 1;
    //    }
    //}



